\section{Problema 2: Replicación de Contenido}

\subsection{Introducción}

Una organización debe implementar una solución de replicación (o sincronización) de contenido para su red de entrega de contenidos en Internet. Dispone de n servidores interconectados mediante m enlaces backbone de alta velocidad.

La primera parte del problema consiste en seleccionar los enlaces de manera que todos los servidores queden conectados optimizando el costo en función del tráfico que transmiten. La segunda parte, consiste en seleccionar cuál debe ser el master (la raíz del árbol de servidores) suponiendo que la replicación tarda el mismo tiempo en atravesar cualquier enlace.

Por ejemplo, para la primera parte:
\begin{verbatim}
INPUT: 
5 8
1 2 10
1 5 15
1 4 30
2 3 20
3 4 50
2 4 35
2 5 10
4 5 30
0

OUTPUT:
70 2 1 2 2 3 2 5 1 4 
\end{verbatim}

%PONER DIBUJITO

\subsection{Desarrollo}

\Large
\textbf{Primera parte}
\normalsize

Consideremos los nodos y las aristas como servidores y conexiones entre los mismos.
Teniendo en cuenta esto, podemos pensar en utilizar un grafo para modelar el problema.
Para resolver el mismo necesitamos encontrar un subgrafo que cumpla con lo siguiente:

\begin{enumerate}
 \item 
 Debe ser conexo, el mesaje debe poder ser transmitido desde cualquier servidor a cualquier otro.
 
 \item
 Debe tener todos los nodos del grafo original (incluir todos los servidores de la red).
 
 \item
 No debe tener ciclos, de tenerlos se estarían utilizando conexiones de más y por ende se obtiene un mayor costo de transmisión.
 
 \item
 La suma del valor de las aristas debe ser el menor posible.
\end{enumerate}

A partir de esto podemos deducir, de 1 y 3 que es un árbol, de 2 que es generador (por ser subgrafo), y de 4 que es mínimo.
Es decir, debemos encontrar el árbol generador mínimo.

Para encontrarlo, vamos a utilizar el algoritmo de Kruskal\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 23.2: The algoritms of Kruskal and Prim}. Éste consiste básicamente en ir eligiendo las aristas de menor peso de manera que al agregarlas al grafo no se formen ciclos.

Otra opción hubiera sido utilizar el \emph{algoritmo de Prim}.
A los efectos del problema (encontrar el AGM) es lo mismo utilizar uno u otro.
Las complejidades temporales en ambos casos no difieren, ni la utilización de alguno de los dos en particular nos brinda alguna facilidad o mejora para resolver el problema.

Tal como hace Kruskal en su implementación optimizada, los servidores se asocian a un \textsl{Disjoint-set}, es decir, a conjuntos que puedan ser identificados por uno de sus miembros (que está destacado)\footnote{ver Cormen, T. and Leiserson, C.E. and Rivest, R.L. and Stein, C., \textsl{Introduction To Algorithms}, MIT-Pess, Cambridge, Massachusets, London, England. Capitulo 6: Graph Algoritm's, Sección 21.1: Disjoint-set operations}. Estos conjuntos contienen a los Servidores , que están representadas por la estructura \textit{Nodo}:

\begin{verbatim}\
typedef struct Nodo{
	Nodo *proximo;
	Nodo *final_lista;
	Nodo *raiz;
	int cantidad_de_elementos;
} Nodo;
\end{verbatim}

A través de la estructura \textit{Nodo} vamos a implementar los \textsl{Disjoint-sets} como listas enlazadas, en la cual \textit{*proximo} va a ser un puntero al proximo elemento del conjunto, \textit{*final\_lista} va a ser un punter al último elemento (el nodo que voy a usar para unir un conjunto nuevo) y \textit{*raiz} va a marcar al elemento distintivo del conjunto (todos los elementos del conjunto apuntan a la misma raíz). El valor \textit{cant\_elementos} (que me marca la cantidad de elementos del conjunto) sólo va a ser utilizados para la raíz de cada conjunto. Para el resto, si quiero saber esta información, bastará con acceder al puntero a la raíz y preguntarle a la raíz.

Los enlaces se representan con la estructura \textit{Enlace}, que contiene el dato de los servidores que une y su costo.

Todos los enlaces son ordenadas en un min\_heap\footnote{El min\_heap se implementa a través de la función make\_heap de la librería algorithms, que toma tres parámetros: un iterador al comienzo de la lista, un iterador que apunta al final y una función booleana que compara dos elementos. En este caso, la función booleana es \textit{trd\_order} compara el costo de los enlaces implementados mediante un struct. Para más referencias, ver http://www.cplusplus.com/reference/algorithm/make\_heap/}. El objetivo de esta estructura es recorrer los enlaces en orden de menor a mayor según el costo de sincronización.

Para cada enlace se va a verificar la siguiente condición: que al seleccionarlo como parte de mi solución no se formen ciclos. Si esto se cumple la guardo en un vector \textit{resultado} y luego junto los nodos enlazados de las dos componentes conexas de esos servidores entre sí. Finalmente actualizo la variable \textit{cantidad\_de\_elementos}, pero sólo para la raíz de la componente conexa (o el elemento que lo identifica).

A continuación se muestra un ejemplo del funcionamiento:

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-1.png}}
\caption{El algoritmo recorre un grafo de 7 servidores nombrados de la A a la G}
\label{fig:grafo1}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-2.png}}
\caption{El algoritmo busca la arista de menor peso y la selecciona (en este caso, hay un empate entre AD y CE)}
\label{fig:grafo2}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-3.png}}
\caption{Luego selecciona la próxima arista de menor peso}
\label{fig:grafo3}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-4.png}}
\caption{La próxima arista de peso mínimo es DF}
\label{fig:grafo4}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-5.png}}
\caption{La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.}
\label{fig:grafo5}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-6.png}}
\caption{El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE), DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).}
\label{fig:grafo6}
\end{figure}

\begin{figure}[here]
\centerline{\includegraphics[scale = 0.7]{ej2-4.png}}
\caption{Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol generador mínimo para el grafo de servidores}
\label{fig:grafo4}
\end{figure}


\Large
\textbf{Problema 2}
\normalsize

Para modelar el problema 2 utilizamos una lista de enlaces y un entero que indica la cantidad de servidores. La entrada de nuestro problema es un árbol de servidores (no tiene ciclos).

Cada servidor se representa mediante la estructura \texttt{NodoArbol}:

\begin{verbatim}
 
typedef struct NodoArbol{
		int numero;
		int grado;
		bool estoyEliminado;
		list<int> adyacencias;
} NodoArbol;

\end{verbatim}

El algoritmo comienza recorriendo los nodos del árbol para encontrar aquellos que sean hojas (es decir, que tengan grado = 1) y las agrega en una lista.

Luego va a ir tomando las hojas una a una y las va a ir eliminando. A medida que las elimina, le resta 1 al grado del nodo padre de la hoja (el único con el que se conecta). Si al restarle uno al nodo del padre se encuentra con que el grado de este es igual a 1, entonces reconoce que el padre se ha convertido en una hoja y lo agrega a una lista nueva.

Cuando termina de recorrer la lista de hojas actuales, repite esta operación para la lista de hojas nuevas (las que se formaron a partir de eliminar las hojas anteriores).

El algoritmo repite esta operación hasta que la cantidad de nodos que queda es menor o igual a 2 (lo que quiere decir que arrancando desde las hojas y subiendo nivel por nivel, estos eran los nodos de mayor altura). Finalmente, si queda un nodo, lo devuelve y si no devuelve cualquiera de los otros dos.

\subsubsection{Código Fuente}

Incluimos a continuación el ciclo principal del código fuente de nuestro algoritmo:

Problema 1:

\begin{verbatim}
 list<Enlace> armar_servidor(vector<Enlace> enlaces, int cantEnlaces, int cantServidores) {
	int primer_serv;
	int segundo_serv;
	
	list<Enlace> resultado;
	
	Nodo *raiz1;
	Nodo *raiz2;
	Nodo *raizAux;
	Nodo *nodoAux;
	
	make_heap(enlaces.begin(), enlaces.end(), trd_order);
	Nodo* servidores[cantServidores];
	
	for(int i = 0; i < cantServidores; i++) {
		Nodo *nodo_servidor = new Nodo;
		nodo_servidor->proximo = NULO;
		nodo_servidor->final_lista = nodo_servidor;
		nodo_servidor->raiz = nodo_servidor;
		nodo_servidor->cantidad_de_elementos = 1;
		
		servidores[i] = nodo_servidor;
	}
	
	for (int k = 0; k < cantEnlaces; k++) {
		//Levanto un enlace
		primer_serv = enlaces.front().primer_servidor;
		segundo_serv = enlaces.front().segundo_servidor;
		
		primer_serv--;
		segundo_serv--;
		
		//Chequeo si no formo un ciclo
		if(servidores[primer_serv]->raiz != servidores[segundo_serv]->raiz) {
		
			raiz1 = servidores[primer_serv]->raiz;
			raiz2 = servidores[segundo_serv]->raiz;
			
			//Me fijo cual es la de longitud más corta	
			if(raiz1->cantidad_de_elementos < raiz2->cantidad_de_elementos) {
				raizAux = raiz1;
				raiz1 = raiz2;
				raiz2 = raizAux;
			}
			
			//Pongo la lista más pequeña atrás de la más grande y actualizo la raiz de la más grande
			(raiz1->final_lista)->proximo = raiz2;
			raiz1->final_lista = raiz2->final_lista;
			raiz1->cantidad_de_elementos += raiz2->cantidad_de_elementos; 
			
			nodoAux = raiz2;
			
			//Actualizo los elementos de la lista más pequeña que estoy agregando
			for(int h = 0; h < raiz2->cantidad_de_elementos; h++) {
				nodoAux->raiz = raiz1;
				nodoAux = nodoAux->proximo;
			}
			
			resultado.push_back(enlaces.front());
			pop_heap(enlaces.begin(), enlaces.end(), trd_order);
			enlaces.pop_back();
		} else {
			pop_heap(enlaces.begin(), enlaces.end(), trd_order);
			enlaces.pop_back();
		}
	}
	
	return resultado;
}
\end{verbatim}


Problema 2:

\begin{verbatim}
 int elegir_raiz(list<Enlace> aristas, int cantServidores){
	vector<NodoArbol> nodos;
	list<int> hojas_actuales_y_futuras;
	list<int> hojas_futuras_y_actuales;
	bool actual_o_futuro(true);
	int nodosRestantes = cantServidores;
	
	int i;
	
	for(i = 0; i < cantServidores; i++){ // O(N)
		NodoArbol nodo;
		nodo.numero = i;
		nodo.grado = 0;
		nodo.estoyEliminado = false;
		nodos.push_back(nodo);
	}
	
	int cantAristas = aristas.size();
	
	for(i = 0; i < cantAristas; i++){ // O(M)
		nodos[aristas.front().primer_servidor - 1].adyacencias.push_back(aristas.front().segundo_servidor);
		nodos[aristas.front().primer_servidor - 1].grado++;
		nodos[aristas.front().segundo_servidor - 1].adyacencias.push_back(aristas.front().primer_servidor);
		nodos[aristas.front().segundo_servidor - 1].grado++;
		aristas.pop_front();
	}
	
	for(i = 0; i < cantServidores; i++){ // O(N)		
		if(nodos[i].grado == 1){
			hojas_actuales_y_futuras.push_back(nodos[i].numero);
		}	
	}

	int padre;
	int padreAux;
	int cantAdyacencias;
	int cantHojas;

	while(nodosRestantes > 2) {
		if(actual_o_futuro) {
			
			//Tomo una hoja
			cantHojas = hojas_actuales_y_futuras.size();

			for(i = 0; i < cantHojas; i++) { // O(N)
				
				//Me fijo cual es el padre
				cantAdyacencias = nodos[hojas_actuales_y_futuras.front()].adyacencias.size();
				list<int>::iterator it = nodos[hojas_actuales_y_futuras.front()].adyacencias.begin();
				
				while(it != nodos[hojas_actuales_y_futuras.front()].adyacencias.end()) {
					if(!(nodos[(*it)-1].estoyEliminado)) {
						padre = *it;
						break;
					}
					it++;
				}
				
				//Le resto uno al grado del padre
				nodos[padre-1].grado--;
				//Si al restarle uno al grado lo convertí en hoja, lo agrego a la otra lista
				if(nodos[padre-1].grado == 1){
					hojas_futuras_y_actuales.push_back(nodos[padre-1].numero);
				}
				//Elimino la hoja
				nodos[hojas_actuales_y_futuras.front()].estoyEliminado = true;
				
				//La saco de la lista
				hojas_actuales_y_futuras.pop_front();
				//Resto uno a la variable de nodos eliminados
				nodosRestantes--;
			
			}
			
			//Cambio de lista
			actual_o_futuro = false;
			
		} else {
			cantHojas = hojas_futuras_y_actuales.size();
			
			for(i = 0; i < cantHojas; i++) {
				cantAdyacencias = nodos[hojas_futuras_y_actuales.front()].adyacencias.size();
				list<int>::iterator it2 = nodos[hojas_futuras_y_actuales.front()].adyacencias.begin();
				
				while(it2 != nodos[hojas_futuras_y_actuales.front()].adyacencias.end()) {
					if(!(nodos[(*it2)-1].estoyEliminado)) {
						padre = *it2;
						break;
					}
					it2++;
				}
				
				nodos[padre-1].grado--;
				if(nodos[padre-1].grado == 1){
					hojas_actuales_y_futuras.push_back(nodos[padre-1].numero);
				}
				nodos[hojas_futuras_y_actuales.front()].estoyEliminado = true;
				hojas_futuras_y_actuales.pop_front();
				nodosRestantes--;
			}
			actual_o_futuro = true;
		}
	}
	
	
	list<int>::iterator it3;
	if(actual_o_futuro) {
		return hojas_actuales_y_futuras.front()+1;
	} else {
		return hojas_futuras_y_actuales.front()+1;
	}
}
\end{verbatim}

\subsection{Correctitud}

\Large
\textbf{Problema 1}
\normalsize

El algoritmo de Kruskal resuelve el problema planteado debido a que minimiza el valor de las aristas necesarias para que todos los nodos estén unidos sin que se formen ciclos (árbol generador mínimo). Esto es exactamente lo que se plantea al requerir que todos los servidores se conecten minimizando el costo total de replicación y transmisión de mensajes a toda la red.

Te debo la demostración del problema 2 para la reentrega.
;)

\subsection{Análisis de complejidad}\label{complejidad3}

\subsubsection{Pseudocódigo}

\subsection{Análisis de casos}

\subsection{Test de performance}

\subsection{Compilar y ejecutar}\label{ejecucion3}
